package com.cet.programmercarl.algorithmperformancanalysis.二叉树.层级遍历;

import java.util.*;

/**
 * @program: algorithm
 * @description: 二叉树层级遍历
 * @author: 陈恩涛
 * @create: 2022-07-14 15:03
 **/
public class LC102 {

    private final List<List<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {
        final TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        System.out.println(new LC102().levelOrder(root));
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        levelOrder2(root, 0);
        return result;
    }

    /**
     * 二叉树层级遍历递归法
     * @param node 树枝节点
     * @param level 层级
     */
    public void levelOrder2(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        if (result.size() <= level) {
            result.add(new ArrayList<>());
        }
        result.get(level).add(node.val);

        levelOrder2(node.left, level + 1);
        levelOrder2(node.right, level + 1);


    }

    /**
     * 二叉树层级遍历迭代法
     * @param node 根节点
     * @return 结果
     */
    public List<List<Integer>> levelOrder1(TreeNode node) {
        if (node == null) {
            return result;
        }
        final Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            // 记录每层节点个数，进行遍历
            int len = queue.size();
            final List<Integer> list = new ArrayList<>();
            while (len > 0) {
                final TreeNode headerNode = queue.poll();
                list.add(headerNode.val);
                if (headerNode.left != null) {
                    queue.offer(headerNode.left);
                }
                if (headerNode.right != null) {
                    queue.offer(headerNode.right);
                }
                len--;
            }
            result.add(list);
        }
        return result;
    }


}
